package com.le.enhance.class1;

import java.util.Arrays;
import java.util.Stack;

/**
 * 可解决问题:
 * 给定两个字符串str1,str2,返回str1包含str2的开始位置
 */
public class Code_01_KMP {

    public static int getIndexOf(String str1, String str2) {
        if (str1 == null || str2 == null || str2.length() < 1 || str1.length() < str2.length()) {
            return -1;
        }
        char[] a = str1.toCharArray();
        char[] b = str2.toCharArray();
        int i = 0; // a
        int j = 0; // b
        int[] next = getNextArray(b);
        System.out.println(Arrays.toString(next));
        while (i < a.length && j < b.length) {
            if (a[i] == b[j]) {
                i++;
                j++;
            } else if (next[j] == -1) { // 0号位置配不上, i++;
                i++;
            } else {
                j = next[j];
            }
        }
        return j == b.length ? i - j : -1;
    }

    /**
     * 返回next数组
     *
     * @param str
     * @return
     */
    public static int[] getNextArray(char[] str) {
        if (str.length == 2) {
            return new int[]{-1, 0};
        }
        int[] next = new int[str.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0; // 跳表位置
        while (i < next.length) {
            if (str[i - 1] == str[cn]) {
                next[i++] = cn++;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str1 = "abcaabababaa";
        String str2 = "abab";
        int index = getIndexOf(str1, str2);
        System.out.println(index);
    }

}
